/*
	左边的所有结点小于根结点,右边的所有结点比根结点大
	称为排序二叉树
	按照中序遍历排序二叉树是递增的
*/

#include<stdio.c>
typedef int ElemType;

typedef struct bstnode
{
	int key;//关键字域
	ElemType data;//数据域
	struct bstnode *Lchild,*Rchild;
}BSTNode;

//查找递归算法
BSTNode *BST_Search1(BSTNode *T,int key)
{
	if (T == NULL)
		return NULL;
	else
	{
		if (key == T -> key)
			return T;
		else if (key < T -> key)
			return BST_Search(T -> Lchild,key);
		else
			return BST_Search(T -> Rchild,key);
	}

}

//查找非递归算法
BSTNode *BST_Search2(BSTNode *T,int key)
{
	BSTNode *p = T;
	while (p != NULL && p -> key != key)
	{
		if (p -> key > key)
			p = p -> Lchild;
		else
			p = p -> Rchild;
	}

	if (p -> key == key)
		return p;
	else
		return NULL;
}

//排序树的插入,递归算法
void InsertBST1(BSTNode *T,int key)
{
	BSTNode *x;
	x = (BSTNode *)malloc(sizeof(BSTNode));
	x -> key = key;
	x -> Lchild = x -> Rchild = NULL;

	if (T == NULL)
		T = x;
	else
	{
		if (T -> key == x -> key)
			return;
		else if (x -> key < T -> key)
			InsertBST(T -> Lchild,key);
		else
			InsertBST(T -> Rchild,key);
	}
}

//排序树的插入,非递归算法
void InsertBST2(BSTNode *T,int key)
{
	BSTNode *x,*p,*q;
	x = (BSTNode *)malloc(sizeof(BSTNode));
	x -> key = key;
	x -> Lchild = x -> Rchild = NULL;

	if (T == NULL)
		T = x;
	else
	{
		p = T;
		while (p != NULL)
		{
			if (p -> key == x -> key)
				return;
			q = p;//q是p的父节点,最后找到的的p是空的,需要一个p

			if (x -> key < p -> key)
				p = p -> Lchild;
			else 
				p = p -> Rchild;
			//一直找到最后为空再插入

			if (x -> key < q -> key)
				q -> Lchild = x;
			else
				q -> Rchild = x;
		}

	}
}

/*
	排序树树的插入
	1.如果结点是叶子结点,直接删除
	2.如果结点只有一个分支,直接删除,将左或者右子树怼上
	3.如果左右结点都有,则用直接前驱或者直接后继代替(中序遍历)
	  如何找到其中序遍历的直接前驱或者直接后继:
	  1.p的左子树的最大值为直接前驱
	  2.p的右子树的最小值为直接后继

*/

void DeleteBST(BSTNode *T,int key)
{
	BSTNode *p = T,*f = NULL,*q,*s;//

	while (p != NULL && p -> key != key)
	{
		//f = p;
		if (key < p -> key)
			p = p -> Lchild;
		else
			p = p -> Rchild;
	}

	if (p == NULL)
		return;
	//先搜索有没有要删除的

	s = p;

	if (p -> Lchild != NULL && p -> Rchild != NULL)
	{
		f = p;

		s = p -> Lchild;

		while (s -> Lchild != NULL)
		{
			f = s;
			s = s -> Rchild;
			//找到左子树最右边的结点
		}

		p -> key = s -> key;
		p -> data = s -> data;
	}

	if (s -> Lchild != NULL)
		q = s -> Lchild;
	else
		q = s -> Rchild;

	if (f == NULL)
		T = q;
	else if (f -> Lchild == s)
		f -> Lchild = q;
	else
		f -> Rchild = q;

	free(s);

}

/*
	判断是否是排序二叉树:
	思路:
	排序二叉树的中序遍历是递增的数列
*/
int pre = -32767;
//全局变量保存当前结点的前一个结点的关键字,初始值为int最小

int JudgeBST(BSTNode *T)
{
	int b1,b2;
	if (T == NULL)
		return 1;
	else
	{
		b1 = JudgeBST(T -> Lchild);
		if (b1 == 0 || pre >= b1 -> data)
			return 0;
		pre = b1 -> data;
		b2 = JudgeBST(T -> Rchild);
		return b2;
	}
}

/*
	求出指定结点在给点排序二叉树中的层次
	思想：
	判断一次不成功的就增加一层
*/

int levelCount(BSTNode *T, BSTNode *s)
{
	int level = 0;
	BSTNode *p = T;
	
	if (p != NULL)
	{
		while (p -> Lchild != NULL && p -> Rchild != NULL)
		{
			if (s -> key < p -> key)
			{	p = p -> Lchild;
				level++;
			}
			else if (s -> key > p -> key)
			{
				p  = p -> Rchild;
				level++;
			}
			
		}
	}	

	return level;
}

/*
	递归查找第k小的元素,时间复杂度 O(log2n)

	结点结构类型
	count(有多少个结点以他为根结点),lchild,rchild

	思想:
	设根结点为*T
	1.T的左子树为空
	  1)右子树非空、k =1 则根结点为第k小的结点
	  2)右子树非空、k!=1 则第k小的数在T的右子树

	2.T的左子树不为空
	  1)左子树的根结点,count=k-1,则T为第k小的结点
	  2)左子树的根结点,count>k-1,则第k小的结点在左子树中
	  3)左子树的根结点,count<k-1,则第k小的结点在右子树中第k-(T -> Lchild -> count +1)
*/

BSTNode searchK(BSTNode *T,int k)
{
	if (T -> Lchild == NULL && k == 1)
	{
		return T;
	}
	else if (T -> Lchild == NULL && K != 1)
	{
		return searchK(T -> Rchild, k - 1);
	}	
	else if (T -> Lchild != NULL && T -> Lchild -> count == k-1)
	{
		return T;
	}		
	else if (T -> Lchild != NULL && T -> Lchild -> count > k-1)
	{
		return searchK(T -> Lchild, k);
	}
	else if (T -> Lchild != NULL && T -> Lchild -> count < k-1)
	{
		return searchK(T -> Rchild, k - T -> Lchild -> count + 1);
	}
}